package com.practice.dsa.interviewclassic6;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 描述
 *
 * @author yaokun.zhang
 * @version 1.0
 * @date 2022-11-08 20:45:29
 */
public class CanPermutePalindrome {

    public boolean canPermutePalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        //记录字符出现的次数
        for(int i = 0; i < s.length(); i++ ){
            putChar(map, s.charAt(i));
        }

        int oddNum = 0;
        for(int cnt : map.values()){
            //为偶数 所有的次数都要是偶数
            if(s.length() % 2 == 0){
                if(cnt % 2 != 0 ){
                    return false;
                }
            }
            //为奇数 奇数只能出现一次，剩下的都是偶数
            else{
                if( cnt % 2 != 0 ){
                    oddNum ++;
                    if(oddNum > 1){
                        return false;
                    }
                }
            }

        }
        return true;
    }

    //存放字符
    public void putChar(Map<Character, Integer> map, char c){
        int count = map.getOrDefault(c, 0);
        map.put(c, ++count);
    }

    public boolean canPermutePalindrome2(String s) {
        Set<Character> set = new HashSet<>();
        //记录字符出现的次数
        for(int i = 0; i < s.length(); i++ ){
            putChar(set, s.charAt(i));
        }
        return set.size() <= 1;
    }

    public void putChar(Set<Character> set, char c){
        if(set.contains(c)){
            set.remove(c);
        }else{
            set.add(c);
        }
    }
}
